1. Field of the Invention
The present invention relates to information management systems and more particularly to an optimistic version number based concurrency control for memory-resident index structures.
2. Description of the Related Art
Database systems use indexes for efficient access to specific data items. Different tree structures, such as B-trees and tries (radix trees) are a method of choice for the indexes. In order to provide safe access by multiple processors at the same time, index trees employ a concurrency control method to protect different parts of the tree from being read or written by a processor while another processor is writing to the same place at the same time.
Concurrency control is important for multiprocessor scalability of an index structure. Typically, concurrency control entails the use of latches to lock a part of the index tree, usually a single node, against reading, writing, or both. The best scalability is attained by concurrency control methods that have a minimum amount of latch collisions, i.e., the same latch being wanted by two or more processors at the same time.
In certain index structures, mainly different trie (radix tree) variants (and also in B-trees), at times only a single pointer in a node is to be updated. This update itself is atomic: if the pointer value is both read and updated at the same time, the reader either gets the whole old or the whole new value. In the optimistic, latch-free index traversal (“OLFIT”) scheme, updating a single pointer value in a node would require a version number update on the node, which in turn causes any concurrent read operation to conflict and retry. With nodes typically containing at least a dozen siblings, all the searches going to the siblings other than the one whose pointer is being updated will get false conflicts, potentially causing at least ten times more false than actual conflicts.
Therefore, there is a need for an efficient index structure and a concurrency control scheme that optimize database management systems against the high cost of invalidating paths that are not updated in a multiprocessing environment.